El Problema P vs. NP

EL PROBLEMA P vs. NP

Uno de los 7 problemas del milenio
“La cuestión más importante de toda la informática y uno de los más importantes de las matemáticas” (Lance Fortnow)

“Un regalo a las matemáticas de la informática” (Steve Smale)

El Problema P vs. NP
La teoría de la complejidad computacional

La teoría de la complejidad computacional estudia la complejidad asociada a los problemas que se resuelven computacionalmente. Para ello, estudia todos los posibles algoritmos que pueden usarse y también clasifica los problemas en función de los recursos computacionales necesarios, que son básicamente de dos tipos:

El tiempo necesario para resolver el problema, que es proporcional (o está directamente relacionado) con el número de pasos u operaciones elementales.
El espacio o memoria necesaria.

Se habla de complejidad temporal y espacial, respectivamente. Otras medidas de complejidad computacional que pueden considerarse, en función del tipo de problema, son: el número de procesadores, la cantidad de datos de comunicación, el número de puertas lógicas, etc.

La teoría de la complejidad computacional difiere de otras teorías y conceptos relacionados:

El análisis algorítmico. Analiza la cantidad de recursos necesarios para un algoritmo particular para resolver un problema.
La complejidad algorítmica. Se define como la longitud del programa más corto que se necesita para generar una entidad matemática.
La teoría de la computabilidad. Se ocupa de la especificación de algoritmos a nivel puramente teórico, sin considerar los recursos necesarios a nivel práctico.

Problemas decidibles e indecidibles

Un problema decidible es un problema cuyo resultado es uno entre dos valores posibles: “sí” o “no”, 0 o 1, verdadero o falso, etc. Por ejemplo, el problema de averiguar si un número es o no primo es decidible.

Un problema indecidible es un problema cuya solución tendría en principio también dos valores posibles, pero que es imposible conocer. El ejemplo paradigmático es el famoso problema de la parada de una máquina de Turing: dada una máquina de Turing M y una entrada w, determinar si M terminará deteniéndose tras un número finito de pasos. Alan Turing demostró que este problema es indecidible. Otro ejemplo es el teorema de incompletud (o indecibilidad) de Gödel: en un sistema axiomático formal que incluya los números naturales, hay sentencias que no se puede demostrar que sean verdaderas o falsas.

Hartmanis & Stearn [1965] demostraron la existencia de problemas decidibles con arbitrariamente alta complejidad computacional. Usaron para ello un método de diagonalización, método que se remonta a Cantor, que lo utilizó para demostrar la no numerabilidad de los números reales.

Tipos de problemas computacionales

De acuerdo con el tiempo necesario para su resolución (complejidad temporal), los problemas computacionales que dependen de una variable x, asociada a la magnitud de la complejidad temporal del problema (normalmente, el tamaño de la entrada), se pueden dividir en dos clases:

Problemas computacionales que se resuelven en tiempo polinómico, es decir, que el tiempo necesario para llegar a la solución o resultado es del tipo c·x^k, o más general, del tipo c₀ + c₁·x + c₂·x² + ... + c_k·x^k, en donde los c_i son constantes. La complejidad temporal, en general, se suele expresar como O(x^r), siendo r un número real (se especifica solo la potencia de mayor exponente y donde la letra “O” significa “del orden de”). Los problemas más sencillos son los del tipo O(x), es decir, de tiempo computacional proporcional a x. Los algoritmos de tiempo polinómico se denominan también “tratables” o “factibles”. Ejemplos:
- La suma de dos números naturales de longitud n se resuelve en tiempo polinómico, en particular en un tiempo proporcional a 2n: O(n).
- El producto de dos números de n cifras requiere un tiempo proporcional a n²: On²). Existe un método optimizado que requiere solo O(n^1,585).
- Dado un número natural n, averiguar si es primo. Su complejidad temporal es O(n).
- Ordenar un conjunto de n elementos tiene complejidad temporal O(n²), aunque también hay métodos optimizados que rebajan el exponente.
- La búsqueda sobre una secuencia de elementos ordenados (por ejemplo, un diccionario), es de complejidad temporal O(ln n).
Problemas que para resolverse necesitan un tiempo exponencial, es decir, que se necesita un tiempo del tipo k·c^x, en donde k y c son números reales. Esta función puede crecer de forma extraordinariamente rápida a medida que aumenta x. La complejidad temporal es O(c^x). Los problemas de tipo combinatorio suelen tener este tipo de complejidad. Los algoritmos de tiempo exponencial se denominan también “intratables” o “no factibles”

Ejemplos de este segundo tipo son:

El problema de la suma de subconjuntos (Subset Sum Problem).
Es un problema de decisión que ilustra muy bien el tema de la complejidad temporal exponencial. Se tiene un conjunto C de números enteros. Hay que determinar si existe algún subconjunto cuyos elementos sumen cero (podría ser cualquier otro número). Por ejemplo, si C={13, 17, −4, −9, 25}, la respuesta es afirmativa porque en el subconjunto {−4, −9, 13} sus elementos suman cero.

Si el conjunto C es de longitud n, el número de subconjuntos es 2ⁿ−1 (excluyendo el conjunto vacío). Por lo tanto, su complejidad temporal es O(2ⁿ). Corresponde al método de la “fuerza bruta”: se van generando sucesivamente cada uno de los subconjuntos y se suman sus elementos. Si en algún momento se obtiene cero como resultado, la respuesta es “Sí” y el proceso se para. Si se llega al final, entonces el resultado es “No”. Con n=64 (el número de casillas del tablero de ajedrez), tenemos la enorme cantidad de 2⁶⁴−1 ≃ 8,4·10³⁷. Suponiendo que tengamos un ordenador que ejecutase 10⁹ operaciones por segundo, el tiempo necesario para su resolución sería del orden de 10¹⁰ billones de años (la edad del universo es del orden de 14.000 millones de años).

Aunque para este problema existen métodos más rápidos que el de la fuerza bruta, todavía no se ha descubierto ningún algoritmo eficiente, es decir, que resuelva el problema en tiempo polinómico.

Este problema en particular tiene la característica siguiente. Si nos dan una hipotética solución del problema, es decir, un determinado conjunto de números D de longitud m, se puede verificar en tiempo polinómico si efectivamente se trata o no de una solución. Solo habría que: 1) verificar que sus elementos pertenecen al conjunto original C; 2) sumar sus elementos y comprobar que su suma es cero. Para ello, efectivamente, se necesitan n·m comparaciones (para ver si existen los elementos de D en C), y otros m−1 pasos para realizar la suma de los elementos de D.
El problema del viajante.
Un viajante tiene que visitar n ciudades. Solo algunas ciudades están conectadas entre sí, pero siempre hay un camino para ir de una ciudad a otra (el grafo es conexo). Hay que buscar un camino cíclico (que se denomina “hamiltoniano”) para, partiendo de una ciudad inicial, visitar el resto de las ciudades y volver al punto de partida, recorriendo un camino de longitud total menor que un valor dado D. No se puede pasar por cada ciudad nada más que una vez. Suponiendo que todas las ciudades están conectadas, el número total posible de caminos es n!, que corresponde al número de permutaciones de las n ciudades. Para 100 ciudades, hasta el ordenador más rápido del mundo tendría que invertir miles de millones de años para encontrar la respuesta.
El problema del encaje de cajas.
Se trata de encajar un conjunto de cajas, de dimensiones conocidas, en un determinado espacio (p.e. el maletero de un coche).
El problema de la factorización.
Es la descomposición de un número natural n en sus factores primos. Exige un tiempo que aumenta exponencialmente con el número de dígitos, en concreto, 2 elevado a la raíz cúbica de n: 2^{n^1/3}. Muchos de los métodos criptográficos se basan precisamente en la dificultad de esta descomposición. El algoritmo RSA utiliza una clave pública que es producto de dos números primos.
El problema del isomorfismo de grafos.
Se tienen dos grafos con el mismo número de vértices y de arcos. Se trata de encontrar una aplicación biyecctiva entre los conjuntos de los vértices de ambos grafos que preserve la estructura, es decir, si A y B son dos vértices adyacentes en un grafo, también lo son en el otro. No se conoce un algoritmo eficiente para el caso general. Si los grafos son árboles existen algoritmos no muy complejos que lo resuelven.
El problema del logaritmo discreto.
El logaritmo discreto de x en base a módulo n es un número y tal que x = a^y (mod. n).
El problema de la satisfacibilidad lógica (SAT).
Se tiene un conjunto de expresiones lógicas de n variables booleanas (expresados solo con los operadores lógicos conjunción, disyunción y negación). Se trata de obtener los valores de esas n variables que cumplen o verifican dichas expresiones lógicas. El espacio de posibles soluciones es 2ⁿ, por lo que su complejidad temporal es O(2ⁿ).
El problema de colorear los vértices de un grafo con solo tres colores, sin que haya dos vértices adyacentes del mismo color.

Las clases P y NP

Se denomina “clase P” a la clase de problemas que pueden resolverse en tiempo polinómico.

Se denomina “clase NP” a la clase de problemas cuya solución puede verificarse en tiempo polinómico.

Según estas dos definiciones, P es un subconjunto de NP (P ⊂ NP), pues si es posible resolver un problema en tiempo polinómico, la solución obtenida también se puede verificar en tiempo polinómico.

Puede ocurrir que para ciertos problemas P, el tiempo de verificación sea el mismo que el de resolución. Por ejemplo, la verificación de la suma de dos números requiere realizar la propia suma. Por lo que, paradójicamente, a veces es más fácil verificar la solución de un problema complejo que el de un problema simple.

Dentro de la clase NP hay problemas fáciles (NP-fácil o NP-easy), los que se resuelven en tiempo polinómico, y problemas difíciles (NP-difícil o NP-hard), los que requieren tiempo exponencial. Según esta definición, NP-fácil = P.

La cuestión P vs. NP

El problema que se plantea es si P = NP o si P ≠ NP, es decir, si todos los problemas cuyas posibles soluciones se pueden calcular en tiempo polinómico, es igual o distinto de los problemas que pueden verificarse en tiempo polinómico.

Por ejemplo, el problema de la suma de subconjuntos es de tipo NP, pero como todavía no se ha encontrado un algoritmo eficiente que resuelva el problema en tiempo polinómico, no sabemos si es de tipo P o no.

La cuestión P =? NP es profunda y básica a la vez. Es una de las cuestiones abiertas más importantes en informática, por sus grandes implicaciones teóricas, prácticas e incluso filosóficas, y que suscita varias interrogantes:

¿Es posible que todos los problemas NP posean algoritmos eficientes y ocurre simplemente que todavía no los hemos descubierto?.
¿Hay un método universal para descubrir una solución eficiente de todo problema NP?. Si existe tal método, puesto que para resolver problemas de gran complejidad temporal se requiere creatividad, quizás lo que se está preguntando realmente es si la creatividad puede automatizarse o no.

Una posible forma de demostrar que P ≠ NP es tratar de encontrar un problema o una clase de problemas en NP−P, es decir que sea NP pero no P.

En cualquier caso, sean P y NP iguales o no, tratar de encontrar la relación existente entre P y NP es fundamental para comprender la naturaleza profunda de la computación.

La clase NP-completa

El problema de la suma de subconjuntos, el problema del viajante y el problema del encaje de cajas son problemas combinatorios que comparten una interesante propiedad: en esencia, en el fondo, “todos son el mismo problema”, en el sentido de que, de existir un algoritmo eficiente para uno de ellos, también existirían algoritmos eficientes para los demás. Esta clase de problemas se denomina “NP-completa” y son los problemas de mayor dificultad de la clase NP. Todavía no se ha encontrado ningún algoritmo eficiente para ninguno de estos problemas. Si se encontrara un algoritmo eficiente para un problema NP-completo, esto implicaría que P = NP.

El descubrimiento de la clase NP-completa constituye un hito de enorme importancia, por varias razones:

Porque es una clase universal, una categoría estándar donde se ubican los problemas difíciles, tanto a nivel teórico como práctico.
Porque clarifica la estructura de la clase NP, al establecer dos categorías opuestas en complejidad: la clases de menor complejidad (P) y de mayor complejidad (NP-completa).
Porque los fenómenos y procesos naturales están en su mayoría en las clases P o NP-completa.

Aparte de los tres problemas mencionados, otros problemas NP-completos son:

El problema de la satisfacibilidad lógica (SAT). Fue el primer problema que se detectó como NP-completo. Fue demostrado por Stephen Cook en su artículo de [1971] (el teorema de Cook), en donde se formalizó el concepto de NP-completo. El SAT sigue siendo NP-completo, incluso con solo tres variables lógicas (problema 3SAT). La mayoría de los problemas NP-completos se reducen, mediante procesos eficientes, al problema SAT, haciéndolos así equivalentes en complejidad temporal. De hecho, muchos problemas se resuelven más eficientemente mediante un “resolvedor SAT” (SAT solver) que mediante un algoritmo especializado.

El teorema de Cook establece lo siguiente: “El problema de la satisfacibilidad booleana (SAT) es NP-completo”. Este teorema también se denomina de Cook-Levin porque también fue demostrado independientemente por Leonid Levin hacia la misma época..
El problema de colorear los vértices de un grafo con solo 3 colores, sin que haya dos vértices adyacentes del mismo color.
El problema Clique (pandilla). Dado un grafo y un entero k, ¿hay k vértices con todos los pares mutuamente adyacentes?.

El problema de la factorización de un número natural, el problema del isomorfismo de grafos y el problema del logaritmo discreto son problemas NP, pero no se ha demostrado aún que sean NP-completos.

Problemas no-NP

En el problema de la suma de subconjuntos, si solo se pide un subconjunto que sume cero, es muy fácil de verificar que se trata de una solución. Si se piden todos los subconjuntos que verifiquen esta propiedad, la verificación exige repetir el proceso de nuevo para ver si se han incluido todas las soluciones. En este caso, el tiempo de resolución (exponencial) y el de verificación es el mismo, como ocurre normalmente con los problemas P.

Y lo mismo ocurre con el problema del viajante. Si solo se nos exige una camino que recorra todas las ciudades con una longitud total menor que una cierta longitud dada D, basta con chequear que el camino es cíclico, que están todas las ciudades y que la suma de distancias es menor que D. Pero si se nos pide el camino cíclico mínimo, la verificación exige repetir el proceso de resolución.

Este tipo de problemas, que requieren tiempo exponencial, tanto en la resolución como en la verificación, no son problemas NP, por lo que se denominan no-NP.

Esquema general de tipos de problemas

Resolución	Verificación	Tipo de problema
Polinómica	Polinómica	NP-fácil = P
Exponencial	Polinómica	NP-difícil ⊃ NP-completo
Exponencial	Exponencial	No-NP

Las dos alternativas (P vs. NP) y sus consecuencias

Si P ≠ NP, entonces:

Existen problemas que no son ni P ni NP-completos. Se llaman “problemas NP-intermedios” (NP-intermediate). El problema de la factorización, el problema de isomorfismo de grafos y el problema del logaritmo discreto, si no pertenecen a la clase P ni a la clase NP-completa, entonces pertenecerían a la clase NP-intermedia.

Si P = NP, entonces las consecuencias serían muy importantes, entre ellas:

Los problemas de complejidad temporal exponencial se reducirían a problemas simples de complejidad temporal polinómica. Esto podría querer decir que lo simple y lo complejo están unidos, que son la misma cosa, que la complejidad realmente no existe, que todo puede reducirse a lo simple.
Podría responder positivamente a la cuestión filosófica general sobre si la creatividad humana puede ser automatizada.
Muchos problemas de optimización tendrían una solución eficiente (problema del viajante, procesos de producción, logística, diseño de chips electrónicos, investigación operativa, etc.).
Transformaría las matemáticas, pues permitiría a un ordenador encontrar, en tiempo polinómico, una demostración formal de casi cualquier teorema.
Mejoría la predicción del tiempo, terremotos, tsunamis y otros fenómenos naturales.
La traducción automática, el reconocimiento del habla y reconocimiento de objetos sería casi perfecta.
La inteligencia artificial sería más fácil de desarrollar y aplicar.
Aceleraría el rendimiento de Internet y podrían abordarse muchos problemas de la red con gran facilidad.
Afectaría a la teoría de la complejidad descriptiva. Ron Fagin demuestró que la complejidad de la clase de problemas NP es la misma que la clase de problemas que se describen en la lógica de predicados de segundo orden. [ver Propiedades  MENTAL, un Lenguaje Simple Fundamento de la Complejidad.]
Afectaría negativamente a la criptografía, pues la encriptación sería fácil de descubrir, pues suele utilizar el método de la factorización de un número natural grande.

Algunas reflexiones y opiniones sobre la cuestión P vs. NP

Es evidente que, tal y como está planteado, se trata de un problema de decisión. Pero quizás esta cuestión sea indecidible. Nos encontraríamos entonces en una situación similar al al problema de la parada de una máquina de Turing o el teorema de incompletud o indecibilidad de Gödel.
En general, la opinión mayoritaria de los teóricos de la complejidad es que P ≠ NP, por tres razones fundamentales:
1. Hay muchos problemas combinatorios de clase NP a los que no se ha encontrado algoritmos de complejidad polinómica, y eso es debido a que lo más probable es que P ≠ NP.
2. La mayoría de los esfuerzos sobre el tema P vs. NP se han dirigido a demostrar que P  NP.
3. Existen muchos indicios cuasi-empíricos que apuntan a que P ≠ NP.
  El término “cuasi-empírico” fue creado por Imre Lakatos para referirse a método matemático que requiere apoyo en la experimentación. Un caso paradigmático es el de la conjetura de Goldbach (todo número par mayor de 2 es la suma de dos números primos). Esta conjetura se ha comprobado que es cierta hasta 10²⁴ con la ayuda de potentes ordenadores.
Para Razborov & Rudich [1997], es posible que esta cuestión sea tan difícil de demostrar debido precisamente a que P  NP y porque el problema de demostrarlo es de clase P.
“Resolver la cuestión P vs. NP puede requerir un cambio de paradigma” (Bhupinder Singh Anand).

Scott Aaronson [2003] es quizás el autor que más cuestiones plantea respecto a este tema:
Se pregunta si P vs. NP podría ser independiente del sistema axiomático formal de la teoría de conjuntos (como la teoría ZF), como ocurre con ciertos problemas matemáticos (como la hipótesis del continuo). Teniendo en cuenta que la cuestión P vs. NP se reduce en definitiva a saber si existe un algoritmo eficiente para el problema SAT (que es el problema NP-completo paradigmático), existen dos posibilidades:
1. Si no existiera un algoritmo eficiente para SAT, sería imposible probar que P vs. NP está en ZF.
2. Si existiera tal algoritmo eficiente, sería imposible demostrar que es eficiente.
“El problema P vs. NP es quizás auto-referencial, pues plantear la cuestión P vs. NP es seguramente un ejemplo de problema NP-difícil”.
“Si creemos que P ≠ NP, queda tan solo una esperanza para resolver problemas NP-completos en tiempo polinómico, a saber, generalizar lo que entendemos por 'computador'”.
“Está claro que una demostración de P ≠ NP, si existe, requeriría técnicas completamente nuevas”.
“Investigar la verdad o falsedad de P ≠ NP es una tarea prácticamente imposible sin investigar antes los medios de investigación”.
“¿Es P vs. NP realmente una cuestión de la lógica o de la combinatoria?.

Las Vías para Disminuir la Complejidad Computacional
Existen dos formas de intentar disminuir la complejidad computacional de los problemas: la vía práctica y la vía teórica.

La vía práctica trata de intentar superar las limitaciones de los ordenadores digitales actuales mediante la utilización de modelos computacionales físicos alternativos, como los siguientes:

Computación analógica.
Un ejemplo de problema computacional complejo que puede resolverse mediante un proceso físico es el problema STP (Steiner Tree Problem) [Garey & Johnson, 1979]. Se trata de un problema NP-completo que consiste en conectar todos los puntos de un grafo de tal manera que la longitud total de los arcos sea mínima. Se puede resolver rápidamente con computación analógica, mediante el proceso físico siguiente: 1) Se cogen dos placas paralelas cuadradas y se unen solo por uno de sus lados; 2) Se colocan n alfileres conectando ambas placas. Los alfileres representan a los puntos del grafo; 3) Se sumerge la estructura en una solución jabonosa y se retira a continuación. La película jabonosa que conecta los alfileres es la solución al problema, porque la naturaleza sigue siempre el principio de máxima economía.
Computación cuántica.
El primer ejemplo de algoritmo cuántico capaz de resolver un problema computacional complejo fue desarrollado por Peter Shor [1996]. Demostró que un hipotético ordenador cuántico podría ser capaz de factorizar un número de n dígitos con complejidad temporal O((log n)³) y complejidad espacial O(log n).
Computación molecular.
Leonard Adleman [1999], el pionero en este área, realizó un experimento con moléculas de ADN en el laboratorio con el que resolvió un pequeño ejemplo del problema del viajante. Para el problema SAT se ha presentado un algoritmo analógico implementado con moléculas de ADN [Takenaka & Hashimoto, 2002].
Computación con membranas (sistemas P).
Los sistemas P son sistemas paralelos que podrían resolver problemas NP-completos de manera eficiente mediante membranas activas capaces de producir un espacio de trabajo exponencial en tiempo exponencial.

La vía teórica trata de utilizar algoritmos eficientes especiales, como los siguientes:

Algoritmos “divide y vencerás” (divide and conquer).
Hace referencia a un refrán popular y que consiste en un proceso de arriba-abajo en el que se divide recursivamente un problema complejo en subproblemas más simples (del mismo tipo o relacionados), tantas veces como sea necesario, hasta llegar a problemas cuya solución sea obvia. La solución del problema principal se construye, en un proceso inverso (de abajo-arriba) a partir de las soluciones simples encontradas.

Es uno de los más importantes paradigmas algorítmicos pues es el fundamento de muchos algoritmos eficientes como: clasificación (Quicksort y Mergesort), multiplicación de números grandes, multiplicación de matrices, análisis sintáctico arriba-abajo (top-down) y la transformada rápida de Fourier. Este algoritmo se conoce desde Euclides, que lo aplicó para obtener el máximo común divisor de dos números, y representa la tendencia natural de búsqueda de la simplicidad oculta en lo aparentemente complejo.
- Quicksort fue inventado por Tony Hoare en 1962. Es un algoritmo muy simple para ordenar una lista numérica o alfabética. Su eficiencia media es O(n·log n), siendo n la longitud de la lista. Consiste en coger un elemento pivote (el primero de la lista) y separar el resto en dos listas, formadas por los elementos menores y mayores que el pivote, respectivamente. En las dos listas se repite otra vez el proceso hasta llegar a listas de un solo elemento.
- Mergesort es un algoritmo inventado por John von Neumann en 1945 para clasificar una lista. Su complejidad temporal es también de O(n·log n). Consiste en lo siguiente: 1) Si la lista es de longitud cero o uno, la lista ya está ordenada; 2) Se divide la lista en dos sublistas del mismo tamaño, aproximadamente: 3) Se clasifica cada sublista recursivamente aplicando Mergesort; 4) Se fusionan las dos sublistas clasificadas en una sola lista ordenada.
- La multiplicación de números grandes fue inventada por Anatoli A. Karatsuba en 1960. Reduce la complejidad temporal desde O(n²) a O(n^log₂3) = O(n^1,585).
- El algoritmo de Volker Strassen para multiplicación de matrices, inventado en 1969, es más rápido que el algoritmo estándar. Consiste en dividir las matrices en submatrices hasta llegar a matrices de un solo elemento, cuya multiplicación es obvia. Este algoritmo animó la búsqueda de algoritmos aún más rápidos, como el de Coppersmith–Winograd (publicado en 1987).
- La transformada rápida de Fourier (Fast Fourier Transform) fue inventado por James W. Cooley y John W. Tukey en 1965. Es uno de los algoritmos más utilizados en matemáticas. Reduce la complejidad temporal desde O(n²) a O(n·log n).
Algoritmos no determinísticos.
Se basan en las relaciones entre las características probabilísticas de ciertos procesos estocásticos y las soluciones de algunos problemas determinados. La ventaja de este método es que su margen de error no depende del número de variables del problema, por lo que es aplicable a problemas complejos con muchos grados de libertad. Pero la principal limitación de este enfoque no-determinístico es la generación de números aleatorios, pues los generadores suelen ser lentos y no siempre fiables. En general, los algoritmos de tiempo polinómico no deterministas son más poderosos que los deterministas.

El ejemplo más representativo es el famoso método de Montecarlo, inventado por Nicholas C. Metropolis, Stanislaw M. Ulam y John von Neumann en 1946.

Feynman [1982] demostró que el problema de la complejidad exponencial expresada mediante probabilidades calculadas se puede reducir a un problema polinómico expresado mediante probabilidades simuladas.
Algoritmos holográficos.
Son una familia de algoritmos inventados por Leslie Valiant que pueden conseguir velocidades exponenciales en cierta clase de problemas. Son de gran interés porque se consideran relevantes en el problema P vs. NP. Se les llama también “algoritmos accidentales”, debido a su cualidad caprichosa e impredecible. Estos algoritmos no tienen relación con la holografía, excepto metafóricamente. Aunque tienen ciertas similitudes con la computación cuántica, usan computación clásica. Su eficacia proviene de la cancelación mutua de muchos sumandos, que evoca a los patrones de interferencia de un holograma y a la superposición cuántica.

Los algoritmos holográficos se usan principalmente para optimizar problemas de grafos, como el problema de la mínima cobertura de vértices (vertex cover). Una cobertura de vértices de un grafo es un conjunto de vértices tales que cada arco del grafo es incidente a al menos un vértice del conjunto. El problema de encontrar la mínima cobertura de vértices es un problema NP-completo y está incluido en la lista de los 21 problemas NP-completos de Karp.

El Problema P vs. NP desde el Paradigma MENTAL
Cuestiones generales

La cuestión filosófica.
Desde un punto de vista filosófico, hay un principio universal que afirma que a nivel profundo no hay diferencias, que desaparecen las fronteras y que todo está conectado y unificado. El problema se reduce entonces a buscar o identificar ese nivel profundo, en este caso, el nivel computacional profundo. Pero si MENTAL representa el máximo nivel de abstracción posible, desde el paradigma de este lenguaje, las clases P y NP deben verse como manifestaciones de algo más profundo y unificado.
El sentido común.
El sentido común nos dice que, en general, calcular una solución de un problema es más difícil que verificarla, aunque ambos procesos sean de tiempo polinómico (pues pueden tener exponentes diferentes). Según este punto de vista, P ≠ NP.
Formalismo vs. intuicionismo.
El problema P vs. NP es demasiado abstracto y génerico como para ser resuelto a un nivel estrictamente formal. A un problema genérico solo se puede responder de forma conceptual/intuitiva.

Una demostración puramente formal o constructiva requeriría una definición formal de los conjuntos P y NP, pero la matemática tradicional no es capaz de ello, pues no puede expresar las propiedades de estos conjuntos. Se necesitaría un lenguaje formal completamente nuevo. Según este punto de vista, si no podemos plantear el problema formalmente, tampoco podemos contestarlo en este mismo nivel.

La demostración de P vs. NP, de existir, tiene que ser muy diferente de las demostraciones normales de las matemáticas. Debería ser creativa, intuitiva, más allá de las demostraciones analíticas y secuenciales habituales. Los viejos métodos no valen. Hay que contemplar el problema desde un punto de vista superior. Como decía Einstein: “Ningún problema puede ser solucionado desde el mismo nivel de conciencia que lo creó”.
La metamatemática.
El problema P vs. NP es un problema metamatemático. Es curioso que necesitemos una demostración matemática para demostrar los límites de la computación. Ocurre como con el teorema de Gödel, que usa la matemática para demostrar los límites de la matemática (en este caso, las limitaciones de los sistemas axiomáticos formales). Al ser un problema de tipo metamatemático, no es extraño suponer que las herramientas matemáticas conocidas sean insuficientes para resolverlo.
Operativo vs. descriptivo.
Quizás los problemas NP-difíciles se puedan resolver no de forma operativa o computacional, sino descriptiva, o mezcla de ambos sistemas. Por ejemplo, la famosa sentencia G de Gödel “Soy indemostrable” no es computable, es inaccesible, pero es describible y representa a una expresión fractal. En MENTAL: (G =: G/I), que representa a la expresión fractal (((G/I)/I)/I)..., siendo I el predicado “indemostrable”.
Algoritmos secuenciales y paralelos.
El problema de los algoritmos tradicionales es que normalmente son secuenciales. En el caso del problema de la suma de subconjuntos, requiere ir generando y analizando sucesivamente cada uno de los subconjuntos. Una solución, si fuera posible, sería generar todos los subconjuntos en paralelo y verificar su suma también en paralelo. Entonces la solución sería inmediata. El problema es que este método requeriría una enorme cantidad de memoria, y además la arquitectura de los ordenadores no está preparada para esta tarea, pues el paralelismo requiere tantos procesadores como procesos paralelos. Sin embargo, todo lo que existe son sistemas paralelos que evolucionan en paralelo (la sociedad, la naturaleza, etc.). La ingeniería de la computación debe tender hacia el desarrollo del paralelismo computacional genérico, para datos y procesos. Por lo tanto, si la memoria no estuviera limitada, el problema “P vs. NP” se reduciría al problema “secuencial vs. paralelo”.

Si no disponemos de memoria suficiente, podemos abordar los problemas de complejidad temporal exponencial mediante algoritmos mixtos secuenciales-paralelos. Por ejemplo, en el problema de la suma de subconjuntos, dividiendo el proceso en n fases. En la primera fase seleccionamos los subconjuntos de 1 elemento, en la segunda los de 2 elementos, etc., hasta llegar a la fase n en que seleccionamos todos los elementos. En cada una de estas fases aplicamos un proceso paralelo.

La cuestión de los dos modos de conciencia

La cuestión P vs. NP es, una vez más, un caso particular de la bipolaridad universal, representado o simbolizado por las características de los dos modos de conciencia de los hemisferios cerebrales. En este caso, los polos son los problemas computacionales NP-fáciles y NP-difíciles. En efecto:

Los problemas NP-fáciles (de tiempo polinómico) se pueden asociar con lo práctico, lo concreto, lo simple, lo comprimido, lo consciente, lo factible, lo cierto, lo exacto, lo eficiente, lo directo, lo lineal, lo racional.
Los problemas NP-difíciles (de tiempo exponencial) se pueden asociar con lo teórico, lo abstracto, lo complejo, lo expandido, lo inconsciente, lo posible, lo aproximado, lo difuso, lo recursivo, lo cíclico, lo intuitivo, lo creativo.

Hay una gradación continua, no hay una frontera concreta entre ambos, sino difusa. En efecto, el problema NP-fácil vs. NP-difícil es difuso si se platea en términos de eficiencia, pues hace equivalente lo eficiente y el tiempo polinómico. Pero los algoritmos de tiempo polinómico no siempre son factibles o tratables. Por ejemplo, un algoritmo que requiera n¹⁰⁰ pasos no podría ejecutarse en un tiempo razonable, incluso con un valor de n pequeño (por ejemplo, 10), pues el número resultante (10¹⁰⁰) es mayor que el número de átomos en el universo (10⁷⁷). Y no todo algoritmo de tiempo exponencial es intratable. La frontera, pues, entre tiempo polinómico y tiempo exponencial es un tanto difusa.

Encontrar un algoritmo eficiente para un problema es traerlo a la conciencia. Pero hay que ir ganando terreno al inconsciente. Este es el proceso de la ciencia, de la conciencia y la evolución. Si un problema NP-difícil no puede resolverse como NP-fácil, hay que intentar optimizarlo, rebajando en lo posible su grado de complejidad temporal.

Para los problemas fáciles (los de tiempo polinómico) basta con utilizar la razón. Los problemas difíciles (en los de tiempo exponencial) nos conducen a espacios amplios, de muchas posibilidades, que desbordan nuestra capacidad normal de análisis, por lo que hay que contemplarlos desde un punto de vista superior y utilizar la creatividad, la intuición y la imaginación, aplicando por ejemplo reglas de tipo heurístico que generen comprensión. La fuerza bruta es la búsqueda a ciegas, sin rumbo, sin conciencia. Cuando hay una heurística, la búsqueda de soluciones se simplifica, hay rumbo, más conciencia del problema, pues en la heurística está codificado el objetivo.

Por lo tanto, la problemática P vs. NP no es más que la problemática universal de los dos modos de conciencia. El punto de encuentro de ambos modos se encuentra en los arquetipos primarios, en las primitivas semánticas universales que representan el supremo nivel de abstracción.

La cuestión del modelo computacional

La máquina de Turing es el modelo computacional habitualmente utilizado como referencia en la cuestión P vs. NP. Este modelo, introducido por Alan Turing en 1936, es de tipo teórico y fue introducido antes de que se construyeran los primeros ordenadores digitales. La máquina de Turing no considera el aspecto de complejidad computacional; solo si se pueden implementar algoritmos que sean capaces de producir un resultado, sin límite de tiempo ni espacio (la cinta ilimitada de la máquina). La máquina de Turing establece los límites de la computación, y ningún modelo computacional alternativo puede superar este límite.

Sin embargo, este modelo es superficial, de bajo nivel, de detalle. No favorece la creatividad, tan necesaria para resolver los problemas NP-difíciles. La alternativa es MENTAL, un lenguaje que aporta un nuevo modelo de computacional basado en grados de libertad, flexible, abierto y creativo. La creatividad máxima surge desde lo profundo, desde el nivel de la suprema abstracción. Desde este modelo, todo los problemas se ven más simples, todo se clarifica y simplifica porque se contempla todo desde las puertas de la conciencia: las primitivas semánticas universales. MENTAL aporta un nuevo paradigma, un paradigma de tipo unificador que nos permite ver con nuevos ojos viejos problemas, en particular el problema P vs. NP.

MENTAL es un lenguaje conceptual, teórico, ideal (como la máquina de Turing), que es independiente de los recursos físicos disponibles. Por ejemplo, si no existen ciertos recursos (como el paralelismo de expresiones), hay que simularlos. Es, en definitiva, el problema de la competencia (o poder computacional teórico) frente a la eficiencia (el poder computacional práctico con los recursos disponibles).

Con MENTAL se pueden crear algoritmos más eficientes y creativos que los tradicionales gracias a sus recursos computacionales flexibles de alto nivel, entre los que podemos destacar:

Paralelismo.
Es tanto espacial como temporal. La evaluación paralela de una expresión es un problema implementador que no implica necesariamente que tengan que existir tantos procesadores como elementos se vayan a evaluar en paralelo.
Expresiones genéricas.
Las expresiones genéricas (parametrizadas o no) permiten definir expresiones virtuales, enlazadas, compartidas, etc). Permiten trabajar con patrones en lugar en lugar de datos o expresiones concretas. Los datos se pueden parametrizar. Pueden establecerse relaciones no-locales. Estas expresiones se pueden manipular, transformar (en expresiones particulares, en expresiones genéricas de orden superior, etc.).
Representación.
La representación (sustitución potencial) permite describir todo tipo de expresiones, incluyendo las de tipo infinito. Esto implica que no es necesario generar todas las expresiones de detalle.
Compartición.
Las expresiones compartidas permiten ahorrar espacio, pues pertenecen simultáneamente a varias expresiones. La compartición es tanto más efectiva cuanto más grandes son los elementos a compartir.
Evaluación parcial.
Evita tener que evaluar una expresión completa. Se puede aplicar a todo tipo de expresiones, incluyendo las genéricas.
Expresiones de orden superior (meta-reglas, expresiones virtuales de expresiones virtuales, expresiones compartidas de expresiones compartidas, etc.).
Expresiones dinámicas.
Permiten implementar algoritmos que se automodifican durante la ejecución. De esta manera los algoritmos son objetos proteicos, capaces de transformarse durante su ejecución.
Expresiones imaginarias, recursivas, fractales y paradójicas.
Metaprogramación.
Es la generación dinámica de subalgoritmos (o procesos en general) con interrelación entre ellos a través del entorno.
Ejecuciones simbólicas o genéricas.
Son ejecuciones con argumentos genéricos, que pueden ser monitorizadas a su vez por otras expresiones genéricas para contabilizar pasos computacionales, realizar atajos, etc. con el fin de extraer conclusiones sobre la complejidad de los algoritmos.

Gracias a estos recursos, la complejidad computacional debe disminuir, en el sentido de necesitar menos recursos temporales y espaciales.

Conclusiones

P no es igual a NP, porque NP-fácil y NP-difícil son dos polos o extremos de la complejidad. Pero ambas clases de complejidad comparten la misma esencia computacional, los mismos arquetipos primarios, las primitivas semánticas universales.
La verdadera naturaleza de la computación no surge de la resolución del problema P vs. NP, sino de la identificación de los recursos profundos, de alto nivel de abstracción que son las primitivas semánticas universales.
El tema P vs. NP es independiente de la axiomática ZF de la teoría de conjuntos. Pero existe una cierta analogía, pues las primitivas semánticas universales desempeñan un papel análogo al de los axiomas de la teoría de conjuntos. Son axiomas semánticos.
Con MENTAL no se obtienen todos los beneficios previstos si se cumpliera que P = NP, pero sí los siguientes:
- Revela cuales son los grados de libertad computacionales, que son los que definen los límites de lo computable (y lo describible) y que representan la verdadera esencia de la computación.
- La complejidad disminuye. Todo es más fácil, todo se simplifica y es más claro.
- Aporta un punto de vista privilegiado, de máxima conciencia, desde el que contemplar la computación. De hecho, la computación es una manifestación de los arquetipos de la conciencia.
- Se favorece la creatividad. La creatividad no se puede automatizar pero puede ser programada. La creatividad es inherente a la naturaleza combinatoria ortogonal de las primitivas.
- Aporta un paradigma universal desde el que se pueden implementar todo tipo de paradigmas específicos.
- La complejidad operativa y la descriptiva están unidas en el mismo marco conceptual (son dos aspectos del lenguaje).
- Los algoritmos son muy compactos (su complejidad algorítmica es menor).
- La inteligencia artificial es más sencilla de desarrollar.
- Es válido para todos los problemas, sean NP o no-NP. Es universal. Todos los problemas los vemos con las mismas “gafas”, que nos proporcionan los máximos recursos computacionales disponibles. Es cuestión nuestra combinar esos recursos de manera creativa para optimizar lo máximo posible cada problema planteado. Cuanto mayor es la complejidad del problema, mayor debe ser el grado de creatividad requerido para resolverlo.

En definitiva, el problema de la complejidad es el problema de encontrar la simplicidad computacional, simplicidad que se logra con los arquetipos de la conciencia. Paradójicamente, la teoría de la complejidad computacional es la teoría de la simplicidad computacional.

Adenda
El premio del Instituto Clay

El 24 de Mayo de 2000, el Instituto Clay de Matemáticas (con sede en Cambridge, Massachusetts), con ocasión de un congreso en París, ofreció un premio de un millón de dólares para la persona que resolviera uno del los “7 problemas del milenio”, problemas que la comunidad matemática considera importantes y a la vez difíciles de resolver. El año 2000 fue declarado por la Unesco “Año Mundial de las Matemáticas”, cien años después de que Hilbert enunciara sus famosos 23 problemas en el Congreso Internacional de Matemáticos, que tuvo lugar también en Paris.

En el año 2003, el matemático ruso Grigori Perelman resolvió uno de ellos: la conjetura de Poincaré (ahora convertido en teorema). Los otros 6 siguen sin resolverse. Uno de ellos es precisamente el problema P vs. NP. Pero se cree que si se resolviera esta problema, probablemente también se resolverían los demás.

Un poco de historia

En 1965, Jack Edmonds propuso una definición formal de “computación eficiente”: ejecución en un número de pasos limitados por un polinomio de una variable asociada a la complejidad del problema, relacionada con los datos de entrada. Dió el primer ejemplo de cómo evitar la fuerza bruta en la búsqueda de soluciones al descubrir un algoritmo eficiente para resolver el problema del “maximun general matching”, con complejidad temporal O(n⁴).
El origen de la cuestión P vs. NP parece remontarse a una carta que escribió Gödel a Von Neumann en 1956, en el que planteaba el problema claramente y que muestra que era consciente de su importancia. Se preguntaba como mejorar el método de la fuerza bruta en general para resolver problemas combinatorios, en especial la demostración de fórmulas del cálculo de predicados. Aparentemente, Gödel veía el problema como análogo al Entscheidungsproblem de Hilbert, pero de tipo finito. No se sabe si Von Neumann (que por entonces se estaba muriendo de cáncer) meditó sobre este problema o si le contestó. La carta manuscrita original y su traducción al inglés se puede ver en el apéndice de [Sipser, 1992].
Stephen Cook [1971] fue el primer científico que planteó formalmente la cuestión P vs. NP en su artículo de 1971 titulado “The complexity of theorem proving procedures” (La complejidad de los procedimientos de demostración de teoremas), en donde planteó el problema SAT (satisfacibilidad lógica) que dio origen al concepto de clase NP-completa y la cuestión P vs. NP. Stephen Cook es también el autor del artículo oficial sobre este problema realizado para el Instituto Clay [Cook, 2000].
El artículo de Richard Karp “Reductibility among combinatorial problems” (Reducibilidad entre problemas combinatorios) [1972] provocó un renovado interés en el artículo de Cook. En su artículo, Karp suministraba una lista de 21 problemas NP-completos. Karp demostró que esos problemas eran NP-completos mediante su reducción (o transformación) a otro problema que ya se había demostrado que era NP-completo: el problema SAT. Cook y Karp recibieron el premio Turing en 1982 y 1985, respectivamente, por sus contribuciones a la teoría de la complejidad computacional.
Leonid Levin [1973] mostró 6 problemas universales de búsqueda secuencial, que eran NP-completos. Su trabajo suministraba una posible vía para encontrar un algoritmo eficiente, lo que implicaría que habría también un algoritmo eficiente para todo problema NP-completo, y por lo tanto, que P = NP.
Garey & Johnson [1979] recopilaron más de 300 problemas NP-completos. Hoy día hay miles de problemas de esta clase de complejidad.

La demostración de Deolalikar de P ≠ NP

Vinay Deolalikar, un matemático indio que trabaja en HP Research Labs en Palo Alto (California), publicó un artículo el 6 Agosto 2010 en el que afirmaba haber demostrado que P ≠ NP. Su demostración se basa en que si ciertos problemas, que se sabe que son NP completos, estuvieran también en P, entonces tendrían propiedades estadísticas imposibles. El artículo de Deolalikar, que ha sido actualizado varias veces para corregir algunos errores que le han detectado, es muy complejo (tiene 102 páginas) y deberá pasar cierto tiempo hasta que su demostración sea totalmente verificada y aceptada.

Lo que es interesante del artículo es que el autor utiliza un nuevo método de investigación, pues combina dos enfoques diferentes: la lógica y la física estadística. Trasladó el problema computacional P vs. NP al mundo de la lógica formal, utilizado la “teoría de modelos finitos” (finite model theory). Se centró en un problema SAT (satisfacibilidad booleana) desde la perspectiva siguiente: si k es el número de expresiones lógicas de n variables booleanas y se eligen al azar un número de n dígitos binarios, ¿cual es la probabilidad de que ese número satisfaga esas expresiones lógicas?. Si k es muy grande y el número de soluciones posibles es pequeño, nunca habrá soluciones correctas, independientemente del tiempo que se invierta. Si k es pequeño y n es grande, siempre habrá soluciones. En un cierto punto intermedio entre ambos extremos hay soluciones y una rica estructura de distribuciones de probabilidad. Según el autor, como las restricciones de los algoritmos de tiempo polinómico son demasiado grandes para producir esta rica estructura, deduce que P ≠ NP.

Bibliografía

Aaronson, Scott. Los límites de la computación cuántica. Investigación y Ciencia, Mayo 2008, pp. 62-69.
Aaronson, Scott. Is P versus NP formally independent?. Bulletin of the European Association for Theorical Computer Science, 81, October 2003. Disponible en Internet.
Adleman, Leonard Max. Molecular Computation of Solutions to Combinatorial Problems. Science, 226, Nov. 1999, pp. 1021-1024.
Arora, Sanjeev; Barak, Boaz. Computational Complexity. Cambridge University Press, 2009.
Baker, Theodore; Gill, John; Solovay, Robert. Relativizations of the P =? NP question. SIAM J. Comput. 4(4), 431-442, 1975.
Clay Mathematics Institute. Millenium prize problems. http://www.claymath.org/
millennium/
Cook, Stephen A. The P versus NP Problem. Clay Mathematics Institute, Cambridge, Massachusetts, 2000. Disponible en Internet.
Cook, Stephen A. The complexity of theorem proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computation (STOC´71), pp. 151-158. ACM Press, 1971. Disponible en Internet.
Deolalikar, Vinay. Sitio web. http://www.hpl.hp.com/
personal/Vinay_Deolalikar/
Edmonds, Jack. Minimum partition of a matroid into independents subsets. Journal of Research of the National Bureau of Standards, 69: 67-72, 1965.
Feynman, Richard P. Simulating Physics with Computers. International Journal of Theoretical Physics, vol. 21. no. 6/7, 1982.
Fortnow, Lance. The Status of the P Versus NP problem. Communications of the ACM, vol. 52, no. 9, pp. 78-86, 2009. Disponible en Internet.
Garey, Michael R.; Johnson, David S. Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.
Gasarch, W. The P =? NP problem. SIGACT News, 33(2):34-47, June 2002.
Goldreich, Oded. P, NP, and NP-Completeness. The Basics of Computational Complexity. Cambrige University Press, 2010.
Hartmanis, J; Stearns, R.E. On the computational complexity of algorithms. Transactions of the AMS 117, 285-306, 1965.
Horowitz, Ellis; Sahni, Sartaj. Computing Partitions with Applications to the Knapsack Problem. JACM, 21(2):277-292, April 1974.
Karp, Richard M. Reductibility among combinatorial problems. En Raymond E. Miller & James W. Thatcher (eds.) Complexity of Computer Computations, Plenum, pp. 85-103, 1972.
Levin, Leonid A. Universal Sequential Search Problems. Problems of Information Transmission, 9(3), 265-266, 1973.
Lipton, Richard J. The P=NP Question and Gödel´s Lost Letter. Springer, 2010.
Rayo, Agustín. Problemas del milenio. Investigación y Ciencia, Abril 2010, pp. 92-93.
Razborov, A.A; Rudich, S. Natural Proofs. Journal of Computer Systems Science, 55:24-35, 1997.
Schöning, Uwe. A uniform approach to obtain diagonal sets in complexity classes. Theoretical Computer Science, 18(1): 95-103, 1982.
Shor, Peter W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. 1996. Disponible en Internet (arXiv).
Sipser, Michael. The History and Status of the P vs. NP Question. Proceedings of the 24th annual ACM Symposium on Theory of Computing, pp. 603-618, 1992. Disponible en Internet.
Takenaka, Yoichi; Hashimoto, Akihiro. An Analog Algorithm for Satisfiability Problem. Fifth International Symposium on Theory and Applications of Satisfiability Testing (SAT2002), pp. 70-77, (Cincinnati, Ohio, USA), 9th, May, 2002. Disponible en Internet.
Wigderson, Avi. P, NP, and Mathematics. A Computational Complexity Perspective. Proceedings of the ICM 06 (Madrid), 1, pp. 665-712, 2006. Disponible en Internet.